package offer.offer02;


/**
 * 结果 100, 100
 * B是A的子结构, 即从A的某一个根节点开始, B的每一个点, 都能在A的这个根节点开始, 找到同样的点
 * 想法: 可不可以先把两个树放到数组里, 再从数组下手?
 */
public class Solution26 {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;
        if(A.val == B.val){
            //当A的根与B的根相同时, 查看B是不是在A里面
            if(isBInA(A, B)) {
                return true;
            }else {
                if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){
                    return true;
                }
            }

        }else {
            if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){
                return true;
            }
        }
        return false;
    }

    public boolean isBInA(TreeNode subA, TreeNode B){
        if(B == null) return true;
        //B不为空的情况下, subA为一个空树, 返回false
        if(subA == null) return false;
        if(B.val == subA.val){
            return isBInA(subA.left, B.left) && isBInA(subA.right, B.right);
        }else {
            return false;
        }
    }
    public static void main(String[] args) {

        TreeNode a = new TreeNode(1);
        a.left = new TreeNode(0);
        a.right = new TreeNode(1);
        a.left.left = new TreeNode(-4);
        a.left.right = new TreeNode(3);

        TreeNode b = new TreeNode(1);
        b.left = new TreeNode(-4);
        System.out.println(new Solution26().isSubStructure(a, b));

    }
//    public TreeNode makeTree(int[] source){
//        if(source.length == 0) return null;
//        TreeNode result = new TreeNode(source[0]);
//
//    }
}


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */